//
//  main.c
//  LinearList
//
//  Created by XAJZ on 2020/3/31.
//  Copyright © 2020 XAJZ. All rights reserved.
//

//此工程主要演示线性表的链式存储

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

/* 存储空间初始分配量 */
#define MAXSIZE 20

#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

//表内元素的类型 假设为 int
typedef int ItemType;
//返回各个函数的操作码
typedef int Status;

//链式表的节点定义
typedef struct Node{
//    数据域
    ItemType data;
//    指针域
    struct Node *next;
}Node;

typedef struct Node* List;

//1.1链表的初始化 注意：一般地，我们可以使用一个空结点放在首元空出表的第一个元素用作“哨兵”。(本示例未使用哨兵)
//在许多算法中，存在“邻居依赖问题”（我自己造的词），在处理当前元素时，要涉及到它旁边那个元素。那如果当前元素是边界元素呢，它没有旁边那个元素，如果不作处理，程序就可能出错；如果对它特别对待，就会增加代码复杂性，还会降低程序效率。应用哨兵，也就是申请若干个多余的元素作为边界元素的邻居，可以完美得解决这个问题。
//同时，哨兵元素可以用来存储一些状态值，或者用作临时变量

Status initList(List *l){
//    生成头结点
    *l = (List)malloc(sizeof(Node));
//    如果存储分配失败，则退出
    if (*l == NULL) exit(ERROR);
//    头结点的指针域置空
    (*l)->next = NULL;
    return SUCCESS;
        
}

//遍历并打印线性表
Status listPrint(List l){
    
    List p = l->next;
    printf("链表输出：");
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return SUCCESS;
}


/// 在i位置插入新的元素 e
/// @param l 链表
/// @param i 位置
/// @param e 新元素
Status listInsert(List *l, int i, ItemType e){
    int j;
    List p, s;
    p = *l;
    j = 1;
//    找到第 i-1 个结点
    while (p && j < i) {
        p = p->next;
        j++;
    }
    
    if(!p || j > i) return ERROR;
    
    s = (List)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return SUCCESS;
}

/// 删除 i 位置的原素
/// @param l 链表
/// @param i 位置
/// @param e 删除元素带回
Status listDelete(List *l, int i, ItemType *e){
    int j;
    List p,q;
    p = (*l);
    j = 1;
    
    //查找第i-1个结点,p指向该结点
    while (p->next && j < i) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i)) return  ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    
    return SUCCESS;
    
}

//3.1 单链表前插入法（头插法）
/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void createListHead(List *l, int n){
    
    List p;
    
    //建立1个带头结点的单链表
    *l = (List)malloc(sizeof(Node));
    (*l)->next = NULL;
    
    //循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        //生成新结点
        p = (List)malloc(sizeof(Node));
       
        //i赋值给新结点的data
        p->data = i;
        //p->next = 头结点的L->next
        p->next = (*l)->next;
        
        //将结点P插入到头结点之后;
        (*l)->next = p;
        
    }
}

//3.2 单链表后插入法(尾插法)
/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void createListTail(List *L, int n){
    
    List p,r;
 
    //建立1个带头结点的单链表
    *L = (List)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *L;
    
    for (int i=0; i<n; i++) {
        
        //生成新结点
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾指针的next = null 【这一步很重要】
    r->next = NULL;
    
}


/// 获取某值
/// @param l 列表
/// @param i 位置
/// @param e 获取元素带回
Status listGet(List l, int i, ItemType *e){
    int j;
    List p;
    p = l->next;
    j = 1;
    
//    找到第 i 个
    while (p && j < i) {
        p = p->next;
        j++;
    }
    
//    没找到
    if (!p || j > i) return ERROR;
    
    *e = p->data;
    
    return SUCCESS;
}

int main(int argc, const char *argv[]){
  
    List l;
    Status lStatus;
    ItemType e;

    lStatus = initList(&l);
    printf("初始化成功？ %d ", lStatus);

    for (int i = 1; i < 7; i++) {
        listInsert(&l, 1, i);
    }
    printf("插入后 \n");
    listPrint(l);

    listDelete(&l, 1, &e);
    printf("删除后：  %d   \n", e);
    listPrint(l);


    listGet(l, 5, &e);
    printf("取出元素为：%d \n",e);

    List l1,l2;

//    头插法
    createListHead(&l1, 20);
    listPrint(l1);

//    尾插法
    createListTail(&l2, 30);
    listPrint(l2);
    
}

